package com.yulan.Tree;

public class LeetCode_124 {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return  maxSum;
    }

    public int maxGain(TreeNode root){
        if(root == null)
            return  0;

        int leftGain = Math.max(maxGain(root.left),0);
        int rightGain = Math.max(maxGain(root.right),0);

        int newGain = root.val + leftGain + rightGain;

        maxSum = Math.max(newGain,maxSum);

        return root.val + Math.max(leftGain,rightGain);
    }
}














